package leetcode;
/**
 * 203.移除链表元素
 * 给你一个链表的头节点 head 和一个整数 val ，
 * 请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
 */
public class Num_203 {
    /** 方法一：用 循环 无头单链表  解决 **/
    public ListNode removeElements1(ListNode head, int val){
        //先删除头节点的val值
        while(head != null && head.val == val){
            head = head.next;
        }
        if(head == null){
            return null;
        }
        //此时head不为空，且一定不是待删值
        ListNode prev = head;
        while(prev.next!=null){
            if(prev.next.val == val){
                prev.next = prev.next.next;
            }else{
                prev = prev.next;
            }
        }
        return head;
    }

    /** 方法二：用 递归 无头单链表  解决 **/
    public ListNode removeElements(ListNode head, int val){
        if(head == null){
            return null;
        }
        //将head.next以及之后的节点交给removeElements去处理
        head.next = removeElements(head.next, val);
        if(head.val == val){
            //如果当前头节点是待删节点，则直接把它的下一个节点作为头节点
            return head.next;
        }
        return head;
    }

    /** 方法三：用 带头单链表解决 **/
    public ListNode removeElements3(ListNode head, int val){
        //建立一个虚拟头节点
        ListNode dummyHead = new ListNode(-1);
        //把虚拟头节点作为链表的头部
        dummyHead.next = head;
        ListNode prev = dummyHead;
        while(prev.next!=null){
            if(prev.next.val == val){
                prev.next = prev.next.next;
            }else{
                prev = prev.next;
            }
        }
        return dummyHead.next;
    }
}

